package com.gxc.heap;

import java.util.*;

/**
 * 给定一个字符串类型的数组arr，求其中出现次数最多的前K个
 *
 * 解法：
 * 1)
 * 维护两个堆，一个大根堆，一个小根堆
 * 首先放入小根堆，堆顶就是出现次数最小的
 * 其余小于小根堆次数的放入大根堆，大根堆次数堆顶就是仅次于K个的最多次数
 * (需要实时更新堆内排序)
 * 2)
 * 准备一个哈希表，key存放字符串，value存放这个字符串出现的次数，准备一个容量为k的小根堆，用词频大小维护，
 * 遍历哈希表，小根堆没满之前入小根堆，满了之后看当前的字符串的value是否大于小根堆堆顶的value，
 * 是则小根堆顶的元素弹出，当前字符串进小根堆，直到遍历完，
 * 把小根堆里的k个字符串弹出就是出现次数最多(词频数最多)的前K个字符串
 */
public class FrontK {

    /**
     * 解法2
     */
    public static PriorityQueue<WordFrequency> compare(String[] strings, int k) {
        Map<String , Integer> wordFrequencyMap = new HashMap<>();
        for (String string : strings) {
            if (wordFrequencyMap.get(string) == null) {
                wordFrequencyMap.put(string, 1);
            } else {
                wordFrequencyMap.put(string, wordFrequencyMap.get(string)+1);
            }
        }
        //小根堆
        PriorityQueue<WordFrequency> frontK = new PriorityQueue<>(new WordFrequencyComparator());

        Iterator<Map.Entry<String, Integer>> iterator = wordFrequencyMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Integer> next = iterator.next();
            if (frontK.isEmpty()) {
                frontK.add(new WordFrequency(next.getKey(), next.getValue()));
            } else if (frontK.size() < k) {
                frontK.add(new WordFrequency(next.getKey(), next.getValue()));
            } else {
                if (next.getValue() > frontK.peek().times) {
                    frontK.poll();
                    frontK.add(new WordFrequency(next.getKey(), next.getValue()));
                }
            }
        }
        return frontK;
    }

    public static class WordFrequencyComparator implements Comparator<WordFrequency> {

        @Override
        public int compare(WordFrequency o1, WordFrequency o2) {
            return o1.times - o2.times;
        }
    }

    public static class WordFrequencyComparator2 implements Comparator<WordFrequency> {

        @Override
        public int compare(WordFrequency o1, WordFrequency o2) {
            return o2.times - o1.times;
        }
    }

}
